import java.util.HashMap;

public class LRU {
    //采用哈希表+双向链表
    //哈希表能用于快速查找该元素是否存在，双向链表进行填充插入元素
    class Node{
        public Node next;
        public Node prev;
        public int key;
        public int value;

        public Node(int key,int value){
            this.key=key;
            this.value=value;
        }
    }

    class NodeList{
        public Node head;
        public Node tail;
        public NodeList(){
            this.head=this.tail=null;
        }
        public void addFirst(Node node){
            // 检查链表是否为空
            if (head == null) {
                // 如果链表为空，则新节点既是头节点也是尾节点
                head = tail = node;
            } else {
                // 如果链表不为空，则将新节点插入到头节点之前
                node.next = head;
                head.prev = node;
                head = node; // 更新头节点为新节点
            }
        }

        public void show(){
            Node current=head;
            while(current!=null){
                System.out.print(current.key+" ");
                current=current.next;
            }
        }

        public Node removeLast() {
            if (tail == null) return null;
            Node node = tail;
            if (head == tail) {
                head = tail = null;
            } else {
                tail = tail.prev;
                tail.next = null;
            }
            return node;
        }


    }
    private int[] origin={4,3,4,2,3,1,4,2};//预备好调入内存的数据

    public static int size=3;//假设内存最大物理块为3
    private HashMap<Integer,Node> map=new HashMap<>();
    private  NodeList nodeList = new NodeList();
    private void LRUcache() {
        int start = 0;
        Node node;
        while (start < origin.length) {
            //缓存满了的话移除表尾元素（最久未访问元素）,将元素K插入表头，增加map中的node, 更新map
            if (map.size() == size) {
                Node evictedNode = nodeList.removeLast();
                map.remove(evictedNode.key);
                node = new Node(origin[start], 1);
                nodeList.addFirst(node);
                map.put(origin[start], node);
            } else if (!map.containsKey(origin[start]) && map.size() < size) {
                //缓存不存在，并且缓存没有满的话，直接把元素插入链表的表头
                node = new Node(origin[start], 1);
                nodeList.addFirst(node);
                map.put(origin[start], node);
            } else if ( map.containsKey(origin[start])) {
                //存在，则把链表中的元素Node<K, V>删除，map中的数据<K, Node<K, V> >不用删除，再在链表头部插入元素，并更新map，直接返回即可
                removenode(start);
            }
                System.out.print(origin[start] + "调入内存，当前内存中元素为:");
                nodeList.show();
                System.out.println();
                start++;
            }
        }

    private void removenode(int start){
        //移出结点
        Node current = nodeList.head;
        while (current != null) {
            if (current.key == origin[start]) {
                if (current == nodeList.head) {
                    nodeList.head = nodeList.head.next;
                } else if (current == nodeList.tail) {
                    nodeList.tail = nodeList.tail.prev;
                    nodeList.tail.next = null;
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                }
                nodeList.addFirst(current);
                break;
            }
            current = current.next;
        }
    }
    public static void main(String[] args) {
        LRU lru=new LRU();
        lru.LRUcache();
    }
}
